#pragma once

#include <math.h>

/*
高效编程的奥秘 部分函数实现
*/

//无分支指令 差或0函数 最大值 最小值函数
#pragma region 

/// <summary>
/// 差或0函数（无分支指令）
/// 当x>y时，返回x-y
/// 当x<y时，返回0
/// </summary>
/// <param name="x"></param>
/// <param name="y"></param>
/// <returns></returns>
extern "C" __declspec(dllexport)
int doz(int x, int y)
{
	int d = x - y;
	return d & ((~(d ^ ((x ^ y) & (d ^ x)))) >> 31);
}

/// <summary>
/// 最大值函数（无分支指令）
/// </summary>
/// <param name="x"></param>
/// <param name="y"></param>
/// <returns></returns>
extern "C" __declspec(dllexport)
int _max(int x, int y)
{
	return y + doz(x, y);
}

/// <summary>
/// 最小值函数（无分支指令）
/// </summary>
/// <param name="x"></param>
/// <param name="y"></param>
/// <returns></returns>
extern "C" __declspec(dllexport)
int _min(int x, int y)
{
	return x - doz(x, y);
}

/// <summary>
/// 无符号版的差或0函数（无分支指令）
/// </summary>
/// <param name="x"></param>
/// <param name="y"></param>
/// <returns></returns>
extern "C" __declspec(dllexport)
unsigned int dozu(unsigned int x, unsigned  int y)
{
	int d = x - y;
	return d & ~((~(d ^ ((~x ^ y) | ((x == y) & d)))) >> 31);
}

/// <summary>
/// 无符号版最大值函数（无分支指令）
/// </summary>
/// <param name="x"></param>
/// <param name="y"></param>
/// <returns></returns>
extern "C" __declspec(dllexport)
unsigned int _maxu(unsigned int x, unsigned int y)
{
	return y + dozu(x, y);
}

/// <summary>
/// 无符号版最小值函数（无分支指令）
/// </summary>
/// <param name="x"></param>
/// <param name="y"></param>
/// <returns></returns>
extern "C" __declspec(dllexport)
unsigned int _minu(unsigned int x, unsigned int y)
{
	return x - dozu(x, y);
}


#pragma endregion

//无分支指令 绝对值函数
#pragma region 

/// <summary>
/// 绝对值函数（无分支指令）
/// </summary>
/// <param name="x"></param>
/// <returns></returns>
extern "C" __declspec(dllexport)
int _abs(int x)
{
	int y = x >> 31;
	int r0 = (x ^ y) - y;
	int r1 = (x + y) ^ y;
	int r2 = x - (x << 1 & y);

	return r0;
}

/// <summary>
/// 负绝对值函数（无分支指令）
/// </summary>
/// <param name="x"></param>
/// <returns></returns>
extern "C" __declspec(dllexport)
int _nabs(int x)
{
	int y = x >> 31;
	int r0 = y - (x ^ y);
	int r1 = (y - x) ^ y;
	int r2 = (x << 1 & y) - x;

	return r0;
}

#pragma endregion

//无分支指令 符号函数 三值比较函数
#pragma region 

extern "C" __declspec(dllexport)
int sign(int x)
{
	/*
	此公式需要无符号右移，即逻辑位移
	在C/C++中
	无符号数，左移和右移都是逻辑位移（空位填0）
	有符号数，左移使用逻辑位移，右移使用算术位移（空位填1）
	*/
	int r0 = -(x >> 31) | (-x >> 31);
	int r1 = (x > 0) - (x < 0);
	int r2 = (x >= 0) - (x <= 0);
	return r1;
}

/// <summary>
/// 符号函数的一般化
/// 若x<y,返回-1
/// 若x=y,返回0
/// 若x>y,返回1
/// </summary>
/// <param name="x"></param>
/// <returns></returns>
extern "C" __declspec(dllexport)
int cmp(int x, int y)
{
	/*
	此公式需要无符号右移，即逻辑位移
	在C/C++中
	无符号数，左移和右移都是逻辑位移（空位填0）
	有符号数，左移使用逻辑位移，右移使用算术位移（空位填1）
	*/
	int r1 = (x > y) - (x < y);
	int r2 = (x >= y) - (x <= y);
	return r1;
}

/// <summary>
/// 符号传递函数,即将y的符号传递给x
/// 若y>=0,返回abs(x)
/// 若y<0,返回-abs(x)
/// </summary>
/// <param name="x"></param>
/// <param name="y"></param>
/// <returns></returns>
extern "C" __declspec(dllexport)
int isign(int x, int y)
{
	/*
	此公式需要无符号右移，即逻辑位移
	在C/C++中
	无符号数，左移和右移都是逻辑位移（空位填0）
	有符号数，左移使用逻辑位移，右移使用算术位移（空位填1）
	*/
	int t1 = y >> 31;
	int r0 = (_abs(x) ^ t1) - t1;
	int r1 = (_abs(x) + t1) ^ t1;

	int t2 = (x ^ y) >> 31;
	int r3 = (x ^ t2) - t2;
	int r4 = (x + t2) ^ t2;
	return r1;
}

#pragma endregion

//交换值问题
#pragma region 

extern "C" __declspec(dllexport)
void swap(int& x, int& y)
{
	x = x ^ y;
	y = x ^ y;
	x = x ^ y;
}

/// <summary>
/// x值只能是参数a和b其中的一个
/// </summary>
/// <param name="x"></param>
/// <param name="a"></param>
/// <param name="b"></param>
/// <returns></returns>
extern "C" __declspec(dllexport)
int SetValues2(int x, int a, int b)
{
	int r0 = a + b - x;
	int r1 = a ^ b ^ x;
	int r2 = x == a ? b : a;
	return r1;
}

extern "C" __declspec(dllexport)
int SetValues3(int x, int a, int b, int c)
{
	int r0 = ((-(x == c)) & a) + ((-(x == a)) & b) + ((-(x == b)) & c);
	int r1 = ((-(x == c)) & (a - c)) + ((-(x == a)) & (b - c)) + c;
	int r2 = ((-(x == c)) & (a ^ c)) ^ ((-(x == a)) & (b ^ c)) ^ c;
	return r0;
}

#pragma endregion

//前导0数目函数和后缀0计数函数
#pragma region 

/// <summary>
/// 前导0数目，二分查找
/// </summary>
/// <param name="x"></param>
/// <returns></returns>
extern "C" __declspec(dllexport)
int nlz(unsigned int x)
{
	int n;
	if (x == 0)
		return 32;
	n = 1;
	if ((x >> 16) == 0)
	{
		n = n + 16;
		x = x << 16;
	}
	if ((x >> 24) == 0)
	{
		n = n + 8;
		x = x << 8;
	}
	if ((x >> 28) == 0)
	{
		n = n + 4;
		x = x << 4;
	}
	if ((x >> 30) == 0)
	{
		n = n + 2;
		x = x << 2;
	}
	n = n - (x >> 31);
	return n;
}

/// <summary>
/// 前导0数目，二分查找，向下计数
/// </summary>
/// <param name="x"></param>
/// <returns></returns>
extern "C" __declspec(dllexport)
int nlz_downcount(unsigned int x)
{
	unsigned int y;
	int n = 32;
	y = x >> 16; if (y != 0) { n = n - 16; x = y; }
	y = x >> 8; if (y != 0) { n = n - 8; x = y; }
	y = x >> 4; if (y != 0) { n = n - 4; x = y; }
	y = x >> 2; if (y != 0) { n = n - 2; x = y; }
	y = x >> 1; if (y != 0) return n - 2;
	return n - x;
}

/// <summary>
/// 前导0数目，二分查找，循环编码
/// </summary>
/// <param name="x"></param>
/// <returns></returns>
extern "C" __declspec(dllexport)
int nlz_while(unsigned int x)
{
	unsigned int y;
	int n, c;
	n = 32;
	c = 16;
	do
	{
		y = x >> c;
		if (y != 0)
		{
			n = n - c;
			x = y;
		}
		c = c >> 1;
	} while (c != 0);
	return n - x;
}

/// <summary>
/// 前导0数目，从两端同时计算
/// </summary>
/// <param name="x"></param>
/// <returns></returns>
extern "C" __declspec(dllexport)
int nlz_both(int x)
{
	int y, n;
	n = 0;
	y = x;
L:	if (x < 0)
	return n;
if (y == 0)
return 32 - n;
n = n + 1;
x = x << 1;
y = y >> 1;
goto L;
}

/// <summary>
/// 前导0数目函数，无分支二分查找
/// 28个基本的RISC指令内执行
/// </summary>
/// <param name="x"></param>
/// <returns></returns>
extern "C" __declspec(dllexport)
int nlz_nobranch(unsigned int x)
{
	int y, m, n;
	y = -(int)(x >> 16);//若x左一半为0，则设置n值为16，若左一半不是0，则设置n值为0，将x右移16位
	m = (y >> 16) & 16;
	n = 16 - m;
	x = x >> m;

	//此时x的形式为000xxxx

	y = x - 0x100; //若8-15位是0，则加4到n，然后将x左移4位
	m = (y >> 16) & 8;
	n = n + m;
	x = x << m;

	y = x - 0x1000;//若12-15位是0，则加4到n，然后将x左移4位
	m = (y >> 16) & 4;
	n = n + m;
	x = x << m;

	y = x - 0x4000;//若14-15位是0，则加2到n，然后将x左移2位
	m = (y >> 16) & 2;
	n = n + m;
	x = x << m;

	y = x >> 14;
	m = y & ~(y >> 1);
	return n + 2 - m;
}

/// <summary>
/// 后缀0计数函数，二分查找
/// </summary>
/// <param name="x"></param>
/// <returns></returns>
extern "C" __declspec(dllexport)
int ntz(int x)
{
	int n;
	if (x == 0)
		return 32;
	n = 1;
	if ((x & 0x0000FFFF) == 0) { n = n + 16; x = x >> 16; }
	if ((x & 0x000000FF) == 0) { n = n + 8; x = x >> 8; }
	if ((x & 0x0000000F) == 0) { n = n + 4; x = x >> 4; }
	if ((x & 0x00000003) == 0) { n = n + 2; x = x >> 2; }
	return n - (x & 1);
}

/// <summary>
/// 后缀0计数函数
/// </summary>
/// <param name="x"></param>
/// <returns></returns>
extern "C" __declspec(dllexport)
int ntz_char(char x)
{
	if (x & 15)
	{
		if (x & 3) {
			if (x & 1) return 0;
			else return 1;
		}
		else if (x & 4) return 2;
		else return 3;
	}
	else if (x & 0x30)
	{
		if (x & 0x10) return 4;
		else return 5;
	}
	else if (x & 0x40) return 6;
	else if (x) return 7;
	else return 8;
}

/// <summary>
/// 后缀0计数函数
/// </summary>
/// <param name="x"></param>
/// <returns></returns>
extern "C" __declspec(dllexport)
int ntz_downcount(unsigned int x)
{
	unsigned int y;
	int n;
	if (x == 0)
		return 32;
	n = 31;
	y = x << 16; if (y != 0) { n = n - 16; x = y; }
	y = x << 8; if (y != 0) { n = n - 8;  x = y; }
	y = x << 4; if (y != 0) { n = n - 4;  x = y; }
	y = x << 2; if (y != 0) { n = n - 2;  x = y; }
	y = x << 1; if (y != 0) { n = n - 1; } // 或者可节省分支但不节省指令数目 n = n - ((x<<1) >> 31);
	return n;
}

/// <summary>
/// 后缀0计数函数
/// </summary>
/// <param name="x"></param>
/// <returns></returns>
extern "C" __declspec(dllexport)
int ntz_while(unsigned int x)
{
	x = ~x & (x - 1);
	int n = 0;
	while (x != 0)
	{
		n = n + 1;
		x = x >> 1;
	}
	return n;
}

/*
后缀0数目函数的应用，“标尺函数”，R.W.Gosper循环检测算法
假设序列X0，X1,...Xn，由X(n+1)=f(Xn)定义，值域有限，则序列必定是循环的
即序列包含一个前导序列X0,X1,...X(u-1),和一个不受限制的循环：X(u),X(u+1),...X(u+r+1),r为循环周期
给定循环函数f,循环检测问题：找到第一个重复元素的下标u和循环周期r
ld_Gosper算法只能输出周期r，以及u的上下限，即:mu_u - mu_l + 1 < max(r-1,1)
*/

/// <summary>
/// ld_Gosper算法
/// </summary>
/// <param name="f">循环函数</param>
/// <param name="x0">初始值</param>
/// <param name="mu_l">重复元素下标的下限</param>
/// <param name="mu_u">重复元素下标的上限</param>
/// <param name="lambda">循环周期</param>
extern "C" __declspec(dllexport)
void ld_Gosper(int (*f)(int), int x0, int* mu_l, int* mu_u, int* lambda)
{
	int Xn, k, m, kmax, n, lgl;
	int T[33];
	T[0] = x0;
	Xn = x0;
	for (n = 1; ; n++)
	{
		Xn = f(Xn);
		kmax = 31 - nlz(n);
		for (k = 0; k <= kmax; k++)
		{
			if (Xn == T[k])
				goto L;
		}
		T[ntz(n + 1)] = Xn;
	}
	//计算 m = max{i | i<n 和 ntz(i+1)=k}
L:	m = ((((n >> k) - 1) | 1) << k) - 1;
	*lambda = n - m;
	lgl = 31 - nlz(*lambda - 1); //Ceil(log2(lambda)) - 1
	*mu_u = m;	//mu上限
	*mu_l = m - _max(1, 1 << lgl) + 1;//mu下限
}

#pragma endregion

// 2的幂边界

//上舍入下舍入到指定的2的幂的倍数
#pragma region 

/// <summary>
/// 向下舍入到指定的2的幂的倍数
/// </summary>
/// <param name="x"></param>
/// <param name="ds2">2的幂的倍数</param>
/// <returns></returns>
extern "C" __declspec(dllexport)
int flp(int x, int ds2)
{
	if (x < 0)
		return x;
	if (x == 0)
		return 0;
	int k = log2(ds2);
	int r0 = x & ((-1) << k); //(x>>k)<<k;需要无符号右移
	return r0;
}

/// <summary>
/// 向上舍入到指定的2的幂的倍数
/// </summary>
/// <param name="x"></param>
/// <param name="ds2">2的幂的倍数</param>
/// <returns></returns>
extern "C" __declspec(dllexport)
int clp(int x, int ds2)
{
	if (x < 0)
		return x;
	if (x == 0)
		return 0;
	int k = log2(ds2);
	int t0 = (1 << k) - 1;
	int r0 = (x + t0) & ~t0;

	int t1 = (-1) << k;
	int r1 = (x - t1 - 1) & t1;

	return r0;
}

/// <summary>
/// 下舍入到下一个2的幂
/// </summary>
/// <param name="x"></param>
/// <returns></returns>
extern "C" __declspec(dllexport)
int flp2(int x)
{
	if (x < 0)
		return x;
	if (x == 0)
		return 0;
	return pow(2, floor(log(x)));
}


/// <summary>
/// 上舍入到下一个2的幂
/// </summary>
/// <param name="x"></param>
/// <returns></returns>
extern "C" __declspec(dllexport)
int clp2(int x)
{
	if (x < 0)
		return x;
	if (x == 0)
		return 0;
	return pow(2, ceil(log(x)));
}

extern "C" __declspec(dllexport)
unsigned int flp2_x1(unsigned int x)
{
	x = x | (x >> 1);
	x = x | (x >> 2);
	x = x | (x >> 4);
	x = x | (x >> 8);
	x = x | (x >> 16);
	return x - (x >> 1);
}

extern "C" __declspec(dllexport)
unsigned int flp2_x2(unsigned int x)
{
	unsigned int y = 0x80000000;
	while (y > x)
	{
		y = y >> 1;
	}
	unsigned int r0 = y;

	unsigned int r1 = 0;
	do
	{
		r1 = x;
		x = x & (x - 1);
	} while (x != 0);

	return r0;
}

/// <summary>
/// 不小于x的最小的2的幂
/// </summary>
/// <param name="x"></param>
/// <returns></returns>
extern "C" __declspec(dllexport)
int clp2_x1(int x)
{
	x = x - 1;
	x = x | (x >> 1);
	x = x | (x >> 2);
	x = x | (x >> 4);
	x = x | (x >> 8);
	x = x | (x >> 16);
	return x + 1;
}

/// <summary>
/// 从地址0开始，内存被划分为大小为2的某个幂的块
/// 对于给定的地址a和长度l，判断a到a+l-1的地址区间是否跨越了块的边界
/// </summary>
/// <param name="addr"></param>
/// <param name="len"></param>
/// <returns></returns>
int overBlock(unsigned int a, unsigned int l,unsigned int blockSize)
{
	//当l=0或1时，a为任意地址都不会跨越边界
	if (l <= 1)
		return 0;
	//当l>块的大小时，任意的地址a都会跨越边界
	if (l > blockSize)
		return 1;
}

#pragma endregion

//算术边界

#pragma region 



#pragma endregion

